package leetcode.code1959;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

	public int minSpaceWastedKResizing(int[] nums, int k) {
		int len = nums.length;
		int[][] dp = new int[len + 1][k + 1];
		int[] presum = new int[len + 1];
		for (int i = 1; i < presum.length; i++) {
			presum[i] = presum[i - 1] + nums[i - 1];
		}
		int[][] sums = new int[len + 1][len + 1];
		int maxAll = Integer.MIN_VALUE;
		for (int i = 1; i <= len; i++) {
			int max = nums[i - 1];
			for (int j = i; j <= len; j++) {
				max = Math.max(max, nums[j - 1]);
				maxAll = Math.max(max, maxAll);
				sums[i][j] = max * (j - i + 1) - presum[j] + presum[i - 1];
			}
		}
		for (int i = len; i >= 1; i--) {
			for (int j = i; j <= len; j++) {
				dp[i][0] += maxAll - nums[j - 1];
			}
		}
		for (int i = len; i >= 1; i--) {
			for (int j = 1; j <= k; j++) {
				int min = Integer.MAX_VALUE;
				for (int p = i; p <= len; p++) {
					int sum = sums[i][p];
					sum += p < len ? dp[p + 1][j - 1] : 0;
					min = Math.min(min, sum);
				}
				dp[i][j] = min;
			}
		}
		return dp[1][k];
	}

	@Override
	public void debug4() {
		H.compare(10, this.minSpaceWastedKResizing(H.str2array3("[10,20,30]"), 1));
		H.compare(10, this.minSpaceWastedKResizing(H.str2array3("[10,20]"), 0));
		H.compare(15, this.minSpaceWastedKResizing(H.str2array3("[10,20,15,30,20]"), 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
